package org.goobs.utils;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.goobs.misc.CFGRule;
import org.goobs.misc.Log;

public class Util {

	protected static final Log LOG = new Log();

	public static final char[] ALPHABET_UPPER = { 'A', 'B', 'C', 'D', 'E', 'F',
			'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S',
			'T', 'U', 'V', 'W', 'X', 'Y', 'Z' };
	public static final char[] ALPHABET_LOWER = { 'a', 'b', 'c', 'd', 'e', 'f',
			'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's',
			't', 'u', 'v', 'w', 'x', 'y', 'z' };

	public static void sleepMili(long mili) {
		try {
			Thread.sleep(mili);
		} catch (InterruptedException e) {
		}
	}

	public static void sleepSeconds(long sec) {
		try {
			Thread.sleep(1000 * sec);
		} catch (InterruptedException e) {
		}
	}

	public static void sleepMinutes(long minutes) {
		try {
			Thread.sleep(1000 * 60 * minutes);
		} catch (InterruptedException e) {
		}
	}

	public static double distance(double a, double b) {
		return Math.sqrt(a * a + b * b);
	}

	public static int compareFilenames(String a, String b) {
		// --Overhead
		char[] first = a.toCharArray();
		char[] second = b.toCharArray();
		// --Check for equality
		for (int i = 0; i < Math.max(first.length, second.length); i++) {
			// (get the characters at the relevant position)
			char c1 = ' ';
			char c2 = ' ';
			if (i < first.length) {
				c1 = first[i];
			}
			if (i < second.length) {
				c2 = second[i];
			}
			// (return if applicable)
			if (c1 < c2) {
				return -1;
			}
			if (c1 > c2) {
				return 1;
			}
			// (otherwise continue)
			continue;
		}

		// --They're equal
		return 0;
	}

	public static String arrayString(Object[] array) {
		StringBuilder b = new StringBuilder();
		b.append("[ ");
		for (Object term : array) {
			b.append(term).append(" ");
		}
		b.append("]");
		return b.toString();
	}

	public static String arrayString(int[] array) {
		StringBuilder b = new StringBuilder();
		b.append("[ ");
		for (int term : array) {
			b.append(term).append(" ");
		}
		b.append("]");
		return b.toString();
	}

	public static String arrayString(double[] array) {
		StringBuilder b = new StringBuilder();
		b.append("[ ");
		for (double term : array) {
			b.append(term).append(" ");
		}
		b.append("]");
		return b.toString();
	}
	
	public static String listString(List <? extends Object> lst){
		StringBuilder b = new StringBuilder();
		b.append("( ");
		for(Object o : lst){
			b.append(o.toString()).append(" ");
		}
		b.append(")");
		return b.toString();
	}

	public static int findIn(String haystack, String needle) {
		char[] transition = needle.toCharArray();
		char[] needleChar = needle.toCharArray();
		char[] haystackChar = haystack.toCharArray();
		int[] epsilon = new int[needle.length()];

		for (int i = 0; i < needle.length(); i++) {
			epsilon[i] = epsilon(needleChar, transition, epsilon,
					needleChar[i], i);
		}
		// print(epsilon);

		int state = 0;
		for (int index = 0; index < haystackChar.length; index++) {
			char c = haystackChar[index];
			while (transition[state] != c && state != 0) {
				state = epsilon[state - 1];
				// System.out.println("   >" + state);
			}
			// System.out.print(c + " : " + state);
			if (transition[state] == c) {
				state++;
			}
			// System.out.println(" -> " + state);
			if (state >= needle.length()) {
				return index - needle.length() + 1;
			}
		}
		return -1;
	}

	private static int epsilon(char[] needle, char[] transition, int[] epsilon,
			char nextChar, int index) {
		// System.out.println(index + " " + nextChar);
		if (index <= 0) {
			return 0;
		}
		int lastEpsilon = epsilon[index - 1];
		if (transition[lastEpsilon] == nextChar) {
			return lastEpsilon + 1;
		} else {
			return epsilon(needle, transition, epsilon, nextChar, lastEpsilon);
		}
	}

	public static int evaluateSimpleArithemetic(String expr) {
		Tree<String> tree = parseArithmeticExpression(expr);
		if (tree == null) {
			throw new IllegalArgumentException("Not a valid expression: "
					+ expr);
		}
		return eval(tree);
	}

	private static int eval(Tree<String> tree) {
		if (tree.isLeaf()) {
			return Integer.parseInt(tree.getItem());
		} else if (tree.childCount() == 1) {
			return eval(tree.getChild(0));
		} else {
			if (tree.getChild(0).getItem().equals("-")) {
				return -1 * eval(tree.getChild(1));
			} else if (tree.getChild(0).equals("(")) {
				return eval(tree.getChild(1));
			} else if (tree.getChild(1).equals("+")) {
				return eval(tree.getChild(0)) + eval(tree.getChild(2));
			} else if (tree.getChild(1).equals("-")) {
				return eval(tree.getChild(0)) - eval(tree.getChild(2));
			} else if (tree.getChild(1).equals("*")) {
				return eval(tree.getChild(0)) * eval(tree.getChild(2));
			} else if (tree.getChild(1).equals("/")) {
				return eval(tree.getChild(0)) / eval(tree.getChild(2));
			} else if (tree.getChild(1).equals("^")) {
				return (int) Math.pow(eval(tree.getChild(0)), eval(tree
						.getChild(2)));
			} else {
				throw new IllegalArgumentException("invalid algebraic form");
			}
		}
	}

	private static HashMap<String, Tree<String>> parseCache;

	public static Tree<String> parseArithmeticExpression(String expr) {
		Set<CFGRule<String>> rules = new HashSet<CFGRule<String>>();
		parseCache = new HashMap<String, Tree<String>>();
		rules.add(new CFGRule<String>("ROOT", new String[] { "S" }));
		rules.add(new CFGRule<String>("ROOT", new String[] { "T" }));
		rules.add(new CFGRule<String>("ROOT", new String[] { "U" }));
		rules.add(new CFGRule<String>("ROOT", new String[] { "V" }));
		rules.add(new CFGRule<String>("S", new String[] { "S", "+", "T" }));
		rules.add(new CFGRule<String>("S", new String[] { "S", "-", "T" }));
		rules.add(new CFGRule<String>("S", new String[] { "T" }));
		rules.add(new CFGRule<String>("T", new String[] { "T", "*", "U" }));
		rules.add(new CFGRule<String>("T", new String[] { "T", "/", "U" }));
		rules.add(new CFGRule<String>("T", new String[] { "U" }));
		rules.add(new CFGRule<String>("U", new String[] { "V", "^", "U" }));
		rules.add(new CFGRule<String>("U", new String[] { "V" }));
		rules.add(new CFGRule<String>("V", new String[] { "(", "S", ")" }));
		rules.add(new CFGRule<String>("V", new String[] { "-", "V" }));
		rules.add(new CFGRule<String>("V", new String[] { "0" }));
		rules.add(new CFGRule<String>("V", new String[] { "1" }));
		rules.add(new CFGRule<String>("V", new String[] { "2" }));
		rules.add(new CFGRule<String>("V", new String[] { "3" }));
		rules.add(new CFGRule<String>("V", new String[] { "4" }));
		rules.add(new CFGRule<String>("V", new String[] { "5" }));
		rules.add(new CFGRule<String>("V", new String[] { "6" }));
		rules.add(new CFGRule<String>("V", new String[] { "7" }));
		rules.add(new CFGRule<String>("V", new String[] { "8" }));
		rules.add(new CFGRule<String>("V", new String[] { "9" }));
		Map<String, Set<CFGRule<String>>> ruleMap = new HashMap<String, Set<CFGRule<String>>>();
		for (CFGRule<String> rule : rules) {
			if (!ruleMap.containsKey(rule.getParent())) {
				ruleMap.put(rule.getParent(), new HashSet<CFGRule<String>>());
			}
			Set<CFGRule<String>> ruleSet = ruleMap.get(rule.getParent());
			ruleSet.add(rule);
		}
		parseCache = null;
		return parse(expr, "ROOT", ruleMap);
	}

	private static Tree<String> parse(String expr, String type,
			Map<String, Set<CFGRule<String>>> rules) {
		String cacheKey = expr + ":" + type;
		if (parseCache.containsKey(cacheKey)) {
			return parseCache.get(cacheKey);
		}
		Set<CFGRule<String>> ruleSet = rules.get(type);
		// --Base case #1
		if (ruleSet == null) {
			if (expr.equals(type)) {
				// System.out.println("true");
				// System.out.println(expr + " is " + type);
				Tree<String> rtn = new Tree<String>(expr);
				parseCache.put(cacheKey, rtn);
				return rtn;
			} else {
				parseCache.put(cacheKey, null);
				return null;
			}
		}
		for (CFGRule<String> rule : ruleSet) {
			// --Base case #2
			if (rule.isSatisfied(expr)) {
				// System.out.println("true");
				// System.out.println(expr + " is " + type);
				Tree<String> rtn = new Tree<String>(expr);
				parseCache.put(cacheKey, rtn);
				return rtn;
			}
			// --Recursive case
			Set<String[]> splits = rule.split(expr);
			for (String[] split : splits) {
				Tree<String> test = new Tree<String>(type);
				for (int i = 0; i < split.length; i++) {
					String e = split[i];
					String tp = rule.getChildren()[i];
					Tree<String> recurse = parse(e, tp, rules);
					if (recurse != null) {
						test.addChild(recurse.copy());
					} else {
						test = null;
						break;
					}
				}
				if (test != null) {
					// System.out.println("true");
					parseCache.put(cacheKey, test);
					return test;
				}
			}
		}

		// System.out.println("false");
		parseCache.put(cacheKey, null);
		return null;
	}
	
	
	public static String stringBetween(String raw, String start, String stop){
		int front = 0;
		if(start != null){
			front = raw.indexOf(start) + start.length();
		}
		int back = raw.length();
		if(stop != null){
			back = raw.indexOf(stop, front);
		}
		if(front < 0 || back < 0){
			return null;
		}
		return raw.substring(front,back);
	}

	public static void main(String[] args) {
		try {
			BufferedReader reader = new BufferedReader(new InputStreamReader(
					System.in));
			String expr = reader.readLine();
			System.out.println(parseArithmeticExpression(expr));
			System.out.println(evaluateSimpleArithemetic(expr));
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
}
